package algorithm.color2w.algorithm.linkedlist;

/**
 * @author wjl <br/>
 * @version 1.0
 * @ClassName: MergeOrderlyLinkedList <br/>
 * @Description: 合并两个有序链表<br />
 * @date: 2020/1/17 15:34<br/>
 */

/*
 *  1.在确保l2.next 不为空的情况下，双指针指向当前要比较的节点
 *  2.如果l2的val大于等于l1的val那么新建临时ListNode存放l2的值，将该节点插入到l1后,并将l2删除，  l2 = l2.next l1=l1.next.next
 *  3.如果l2的val小于l1的val，那么同样新建临时ListNode存放l2的值，将该节点插入到l1前，将l2删除， l2 = l2.next l1=l1.next
 *    - 将节点插入到当前节点的前面可以参照 如何删除当前自己节点的方法。
 *  -------------------------------------------------------------------------------------------------pass
 *  首先，我们设定一个哨兵节点 "prehead" ，这可以在最后让我们比较容易地返回合并后的链表。
 *  我们维护一个 prev 指针，我们需要做的是调整它的 next 指针。
 *  while( l1 或者 l2 指向了 null )
 *      {
 *          如果 l1 当前位置的值小于等于 l2 ，我们就把 l1 的值接在 prev 节点的后面同时将 l1 指针往后移一个。
 *          否则，我们对 l2 做同样的操作。
 *      }
 *      不管我们将哪一个元素接在了后面，我们都把 prev 向后移一个元素;
 *
 *
 */
public class MergeOrderlyLinkedList {

    //   Definition for singly-linked list.
    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    // l1 {1,2,4,5}    l2 {1,3,6,8}
    public static void main(String[] args) {
        ListNode l1Head = new ListNode(1);
        ListNode l10 = new ListNode(2);
        ListNode l11 = new ListNode(4);
        ListNode l12 = new ListNode(5);
        l1Head.next = l10;
        l10.next = l11;
        l11.next = l12;
        ListNode l2Head = new ListNode(1);
        ListNode l20 = new ListNode(3);
        ListNode l21 = new ListNode(6);
        ListNode l22 = new ListNode(8);

        l2Head.next = l20;
        l20.next = l21;
        l21.next = l22;

        l1Head = mergeTwoLists3(l1Head, l2Head);
        while (l1Head != null) {
            System.out.print(l1Head.val + "-");
            l1Head = l1Head.next;
        }


    }

    // l1 {1,2,4,5}    l2 {1,3,6,8}
    // 1.最笨的方法
    public static ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
        ListNode head = l1;
        // 需要考虑l1的长度远远小于l2的时候会出现的情况
        while (null != l2.next) {
//            ListNode curr1Node = l1;
//            ListNode curr2Node = l2;
            ListNode tempNode = new ListNode(-1);
            if (l1.val <= l2.val) {

                //将节点插入到l1后面
                tempNode.val = l2.val;
                tempNode.next = l1.next;
                l1.next = tempNode;
//                while(l1.next != null && l1.next.val < l1.val){
//                    int temp = l1.val;
//                    l1.val = l1.next.val;
//                    l1.next.val = temp;
//                    l1 = l1.next;
//                }

                //将l2节点删除
                l2.val = l2.next.val;
                l2.next = l2.next.next;
            } else {

                //将l1节点的val和tempNode的值做替换，为了将tempNode的插入到l1前面
                tempNode.val = l2.val;
                int temp = l1.val;
                l1.val = tempNode.val;
                tempNode.val = temp;

                //将节点插入到l1前面
                tempNode.next = l1.next;
                l1.next = tempNode;
                l1 = tempNode.next;

                //将l2节点删除
                l2.val = l2.next.val;
                l2.next = l2.next.next;
            }
        }
        return head;
    }

    // 2.哨兵 跟踪迭代
    // l1 {1,2,4,5}    l2 {1,3,6,8}
    public static ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(-1);
//        head.next = l1.val<l2.val?l1:l2;
        ListNode prev = head;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        prev.next = l1 == null ? l2 : l1;
        return head.next;
    }

    //3. 递归
    //   {list1[0]+merge(list1[1:],list2)  list1[0]<list2[0]
    //   {list2[0]+merge(list1,list2[1:])  otherwise
    // l1 {1, 2, 4, 5}
    // l2 {2, 3, 6, 8}
    /*
        我们直接将以上递归过程建模，首先考虑边界情况。
        特殊的，如果 l1 或者 l2 一开始就是 null ，那么没有任何操作需要合并，所以我们只需要返回非空链表。
        否则，我们要判断 l1 和 l2 哪一个的头元素更小，然后递归地决定下一个添加到结果里的值。
        如果两个链表都是空的，那么过程终止，所以递归过程最终一定会终止。
     */
    public static ListNode mergeTwoLists3(ListNode l1, ListNode l2) {
        if (null == l1){
            return l2;
        }else if (null == l2){
            return l1;
        }else if (l1.val < l2.val){
            l1.next = mergeTwoLists3(l1.next,l2);
            return l1;
        }else{
            l2.next = mergeTwoLists3(l1,l2.next);
            return l2;
        }
    }
}
